Linearly many faults in 2-tree-generated networks

摘要

In this article we consider a class of Cayley graphs that are generated by certain 3-cycles on the alternating group A n . These graphs are generalizations of the alternating group graph A G n . We look at the case when the 3-cycles form a “tree-like structure,” and analyze its fault resiliency. We present a number of structural theorems and prove that even with linearly many vertices deleted, the remaining graph has a large connected component containing almost all vertices. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010